package sort;

public class Search {



    /**
     * 1，基本查找
     */
    private static int sequenceSearch(int[] array, int target) {
        for (int i = 0; i < array.length; i++) {
            if (target == array[i]) {
                return i;
            }
        }
        return -1;
    }


    /**
     * 2，二分查找
     */
//迭代
    static int binarySearch1(int arr[], int len, int target) {
        /*初始化左右搜索边界*/
        int left = 0, right = len - 1;
        int mid;
        while (left <= right) {
            /*中间位置：两边界元素之和/2向下取整*/
            mid = (left + right) / 2;
            /*arr[mid]大于target，即要寻找的元素在左半边，所以需要设定右边界为mid-1，搜索左半边*/
            if (target < arr[mid]) {
                right = mid - 1;
                /*arr[mid]小于target，即要寻找的元素在右半边，所以需要设定左边界为mid+1，搜索右半边*/
            } else if (target > arr[mid]) {
                left = mid + 1;
                /*搜索到对应元素*/
            } else if (target == arr[mid]) {
                return mid;
            }
        }
        /*搜索不到返回-1*/
        return -1;
    }


    //递归
    static int binarySearch2(int array[], int left, int right, int target) {
        if (left <= right) {
            int mid = (left + right) / 2;
            /*搜索到对应元素*/
            if (array[mid] == target) {
                return mid;
            } else if (array[mid] < target) {
                /*array[mid]小于target，即要寻找的元素在右半边，所以需要设定左边界为mid+1，搜索右半边*/
                return binarySearch2(array, mid + 1, right, target);
            } else {
                /*array[mid]大于target，即要寻找的元素在左半边，所以需要设定右边界为mid-1，搜索左半边*/
                return binarySearch2(array, left, mid - 1, target);
            }
        } else {
            return -1;
        }
    }


    /**
     *3，插值查找
     * 主要就是修改了mid的计算方式，取值下标是预估 target在整个数组里面所占的比例
     * 适用于数据量大   分布均匀一些  查找效率高
     */
    private static int insertSearch1(int arr[],int target){
        /*初始化左右搜索边界*/
        int low=0,top=arr.length-1;
        int mid;
        while(low<=top){
            mid=low+(target-arr[low])/(arr[top]-arr[low])*(top-low);

            /*arr[mid]大于target，即要寻找的元素在左半边，所以需要设定右边界为mid-1，搜索左半边*/
            if(target<arr[mid]){
                top=mid-1;
                /*arr[mid]小于target，即要寻找的元素在右半边，所以需要设定左边界为mid+1，搜索右半边*/
            }else if(target>arr[mid]){
                low=mid+1;
                /*搜索到对应元素*/
            }else if(target==arr[mid]){
                return mid;
            }
        }
        /*搜索不到返回-1*/
        return -1;
    }



    /**
     *4，斐波那契查找
     */


    /**
     *5，分块查找
     */

    /**
     *6，哈希查找
     */


    /**
     *7，树表查找
     */


}
